from typing import List


class Solution:
    _MAX = 10 ** 9

    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
        n, m = len(nums), len(multipliers)

        # 定义状态矩阵：dp[i][j] 前面移除i个，后面移除j个时的最大分数
        dp = [[-self._MAX] * (m + 1) for _ in range(m + 1)]
        dp[0][0] = 0

        for k in range(m):  # 遍历之前被移除的总数
            for i in range(k + 1):  # 遍历前面被移除的数量
                j = k - i

                # 状态转移
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + nums[i] * multipliers[k])
                dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + nums[n - j - 1] * multipliers[k])

        # 计算最终结果
        ans = -self._MAX
        for i in range(m + 1):
            j = m - i
            ans = max(ans, dp[i][j])
        return ans


if __name__ == "__main__":
    print(Solution().maximumScore(nums=[1, 2, 3], multipliers=[3, 2, 1]))  # 14
    print(Solution().maximumScore(nums=[-5, -3, -3, -2, 7, 1], multipliers=[-10, -5, 3, 4, 6]))  # 102

    # 测试用例60/62
    print(Solution().maximumScore(nums=[172, -967, -632], multipliers=[3, -536]))  # 518828

    # 测试用例44/62
    # -18334745
    print(Solution().maximumScore(
        nums=
        [79, 363, 510, 152, 324, 411, 406, 202, 816, 382, 515, 166, 429, 642, 847, 375, 927, 407, 539, 777, 144, 802,
         656, 548, 515, 211, 97, 64, 302, 57, 500, 660, 978, 655, 940, 116, 622, 58, 315, 733, 487, 921, 989, 744, 276,
         754, 540, 34, 60, 167, 412, 230, 50, 202, 116, 275, 259, 365, 680, 516, 997, 995, 638, 979, 216, 200, 843, 214,
         982, 709, 15, 597, 87, 315, 677, 179, 408, 321, 191, 744, 680, 318, 928, 396, 101, 611, 304, 30, 195, 251, 314,
         696, 211, 156, 399, 441, 471, 856, 585, 624, 483, 56, 731, 829, 907, 888, 498, 139, 869, 441, 96, 686, 487,
         259, 103, 281, 145, 222, 375, 703, 537, 373, 402, 287, 380, 750, 864, 801, 988, 689, 762, 766, 197, 763, 307,
         810, 814, 60, 389, 880, 852, 446, 394, 811, 471, 723, 799, 967, 680, 686, 277, 623, 366, 208, 753, 980, 88,
         943, 639, 605, 808, 990, 249, 278, 694, 681, 956, 844, 637, 49, 19, 126, 180, 640, 239, 938, 295, 270, 257,
         719, 429, 27, 206, 312, 601, 11, 436, 662, 414, 456, 33, 222, 555, 323, 677, 455, 115, 981, 678, 755, 427, 364,
         230, 907, 125, 87, 169, 281, 156, 495, 253, 519, 421, 296, 570, 990, 393, 448, 807, 912, 110, 786, 707, 654,
         828, 765, 913, 864, 951, 735, 297, 831, 153, -763, 46, 385, 179, -279, -395, -675, 319, 272, 92, 565, -184,
         118, -439, 290, 138, -973, -334],
        multipliers=
        [-119, -958, -222, -391, -178, 676, -494, -982, -223, -423, -354, -310, -470, -943, -424, -520, -586, -428, 701,
         -262, -641, -872, -510, -563, -59, -548, -808, -194, -801, 223, -378, -354, -705, -651, -250, -484, -891, -24,
         -298, -369, -181, -957, -503, -935, -118, -551, -808, -742, -331, -518, -393, -226, -647, -547, -468, -678,
         -939, -619, -222, -46, -922, -541, -702, -692, -106, -212, -680, -462, 120, -581, -166, -491, -190, -29, -84,
         -562, -608, -214, -936, -226, -983, -277, -842, 703, -162, -208, -501, -236, -988, -792, -749, -162, -795,
         -142, -340, -577, -936, 763, -103, -467, -426, -446, -283, -664, -814, -63, -147, -621, -659, -855, -823, -920,
         -38, -951, -842, -287, -770, -976, -212, -362, -898, 951, -624, -506, -250, -31, -177, -356, -479, -228, -508,
         -737, -920, -116, -456, -196, -613, -208, 829, -419, -485, -896, -528, -306, -973, -361, -585, -832, -102, -87,
         -119, -534, -38, -330, -1000, -805, -835, -407, -398, -749, -289, -625, -436, -646, -928, -811, -328, -950,
         -916, -594, -772, -903, -741, -348, -809, -839, 531, -667, -960, -396, -518, -524]))
